/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class SubtreeofAnotherTree {
	  public class TreeNode {
		      int val;
		      TreeNode left;
		      TreeNode right;
		      TreeNode(int x) { val = x; }
	  }
	//[3,4,5,1,null,2]
	//[3,1,2] should false
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s==null&&t==null){
        	return true;
        }
        if(s==null||t==null){
        	return false;
        }
        boolean result=false;
        result=isSameTree(s, t);
        if(!result){
        	result=isSubtree(s.left,t);
        }
        if(!result){
        	result=isSubtree(s.right,t);
        }
        return result;
    }
	private boolean isSameTree(TreeNode root1, TreeNode root2) {
		if(root1==null&&root2==null){
			return true;
		}
		if(root1==null||root2==null){
			return false;
		}
		return root1.val==root2.val&&isSameTree(root1.left, root2.left)&&isSameTree(root1.right, root2.right);
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
	}

}
